package com.tgy.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

public class _剑指_Offer_40_最小的k个数 {

    public static int[] getLeastNumbers(int[] arr, int k) {

        if (k == 0) {

            return new int[]{};
        }

        int len = arr.length;
        if (k == len) {

            return arr;
        }

        /**
         * 默认是小顶堆
         */
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((x1,x2)->{

            return Integer.compare(x2,x1);
        });

        for (int i : arr) {

            if (priorityQueue.size() < k) {

                priorityQueue.add(i);
            }else {

                Integer topVal = priorityQueue.peek();

                if (i < topVal) {

                    priorityQueue.poll();
                    priorityQueue.add(i);
                }

            }


        }

        int[] res = new int[k];

        int index = 0;

        while (!priorityQueue.isEmpty()) {

            res[index] = priorityQueue.poll();
            index++;
        }

        return res;
    }

    public static void main(String[] args) {

        int[] nums = {3,2,1};
        System.out.println(Arrays.toString(getLeastNumbers(nums, 2)));
    }
}
